Message authentication codes (MACs) are pieces of information used to authenticate messages. Inputs for an algorithm to generate a MAC are a secret key and the message to be authenticated. Cipher-based MACs (CMAC) are block cipher-based message authentication codes and are described, for instance, in NIST (The National Institute of Standards and Technology) special publication 800-38B, May 2005.
The CMAC on a message is constructed by splitting it into blocks of size equal to the blocksize of the underlying cipher, for instance, 128 bits in the case of the Advanced Encryption Standard (AES), Cipher Block Chaining (CBC)-encrypting the message (with padding in the last block if required), and retaining (all or part of) the result of the last block encryption as the computed MAC value.
To avoid certain classes of attack, the last block is subjected, before ciphering, to an exclusive disjunction (XORing) with one of two possible “subkey” values, usually denoted as K1 or K2, derived from an encryption of the zero vector under the key in use. The choice of which subkey to use is determined by whether the last message block contains padding or not. The subkey values can only be computed by parties knowing the cipher key in use.
If the MAC is shorter than the cipher blocksize, then the standard dictates that the computed MAC should be truncated by retaining the required number of most significant bits.
If a MAC is computed on a message of size less than or equal to the cipher blocksize, then the last block is also the first block, so the modification by subkey XORing is performed on this single block. This means that the direct input to the block operation of the cipher during this MAC computation is not known to an external observer.
FIG. 1 shows a state array 1 and its byte numbering in accordance with the AES disclosed in Federal Information Processing Standard (FIPS) publication 197, Nov. 26, 2001.
The AES cipher operates on the state array 1 of bytes, which is of size 4 bytes by 4 bytes and has byte entries Sr, c, wherein the index “r” references the relevant row and the index “c” references the relevant column of the state array 1. When representing the outputs of an AES cipher operation as a bit-string, the bytes are ordered as follows:
S0,0 S1,0 S2,0 S3,0 S0,1 S1,1 S2,1 S3,1 S0,2 S1,2 S2,2 S3,2 S0,3 S1,3 S2,3 S3,3 
Subsequently, the bytes of this bit-string are numbered according to a convention in which s15 is the leftmost or most significant byte and s0 is the rightmost or least significant byte, so thatsr, c=s15−(4c+r) 
The standard method for truncation of a MAC in accordance with the aforementioned NIST standard is to retain the required number of most significant bits. Accordingly, truncation of an AES-based MAC to 8 bytes corresponds to retention of final state bytes s15 to s8 inclusive.
FIG. 2 shows as an example a 16-byte AES state during the final round of a MAC computation according to the standard. At the start of a so-called Cipher, an initial Round Key 21 is added to the state array 1 of FIG. 1 in order to generate a state array 22 (AddRoundKey operation). The state array 22 is subjected to a ShiftBytes transformation to generate a first transformed state array 23, which is subjected to a ShiftRow transformation to generate a second transformed state array 24. Then, a further Round Key 26 is added to the second transformed state array 24 by XORing each column of the State of the second transformed state array 24 with a word from a key schedule to generate an output state array 25 comprised of rows 31-34 and columns 41-44. The state array 25 is utilized for computing the CMAC in accordance with the standard by retaining the 8 most significant bytes s15 to s8 after truncation and the remaining bytes are discarded. The 8 most significant bytes 27 s15 to s8 are illustrated shaded.
The arrays 22-24 show the corresponding bytes before the effect of the ShiftRows and SubBytes operations of the final round. So, based on observations of the shaded output bytes and hypotheses about the corresponding positions in the final Round Key 26 array, a Differential Power Analysis (DPA) attacker is able to recover some bytes of the Round Keys 21, 26.
At this stage, the attacker can gather additional information about the 2nd-last round key, since he/she can compute the AES key expansion in reverse order.
The AES key expansion algorithm can be written in the formwn-4=T(wn-1)<+>wn 
wherein wn is a 32-bit word corresponding to a column of the Round Key 21, 26 array, “<+>” denotes the “exclusive-OR” operation, and T( ) is a conditional transformation such thatT(wn)=S(wn<<<8)<+>Rconst; if n=0 mod 4, or T(wn)=wn otherwise
<<<8 denotes left rotation by 8 bit positions, S( ) denotes bytewise application of SubBytes, and Rconst is a round constant which varies per round but is known.
With this combination of bytes, running the key expansion algorithm forwards again yields further final round key bytes. At this point, the attacker can proceed no further without considerable difficulty. The operation preceding the 2nd-last round key insertion is a MixColumns, and with only two bytes/column available at the input to SubBytes, the equations required to construct DPA selection functions based on earlier bytes are underdetermined. However, he/she has already reduced the attack complexity to only 240 (since only 5 bytes of the last round key remain unknown) and at this level the remaining key bytes could easily be recovered by a brute force attack.